#pragma
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
//一、插入排序
//1.1 直接插入排序
void insert_sort(int a[], int n)
{
    // tmp表示要插入的元素
    // end表示已插入元素最后一个元素的下标
    int tmp, end;
    // 1个元素默认有序，因此从1开始
    for (int i = 1; i < n; i++)
    {
        tmp = a[i];
        end = i - 1;
        while (end >= 0)
        {
            // 1. 如果a[end] > tmp， 则a[end]向后移, end--
            // 如果a[end] <= tmp，则a[end+1] = tmp
            // 特殊情况：如果tmp是最小的数，则end = -1会跳出循环，因此在循环体外赋值
            if (a[end] > tmp)
            {
                a[end + 1] = a[end];
                end--;
            }
            else
                break;
        }
        a[end + 1] = tmp;
    }
}
//1.2 折半插入排序
void mid_insert_sort(int a[], int n)
{
    int tmp, end;
    for (int i = 1; i < n; i++)
    {
        tmp = a[i];
        end = i - 1;
        // 折半查找
        int l = -1, r = i;
        while (l + 1 != r)
        {
            int mid = l + r >> 1;
            if (a[mid] > tmp) r = mid;
            else l = mid;
        }
        // [0 l] [r i-1], l+1的地方插入，后移[l+1, i-1]一位
        while (end >= l + 1)
        {
            a[end + 1] = a[end];
            --end;
        }
        a[l + 1] = tmp;
    }
}
//1.3 希尔排序

#ifdef SHELL_SORT_ONE
void shell_sort(int a[], int n)
{
    int gap = n;
    while (gap > 1)
    {
        gap /= 2;
        //1. 分组
        for (int i = 0; i < gap; i++)
        {
            // 2. 单组插入排序
            int tmp, end;
            for (int j = i+gap; j < n; j += gap)
            {
                tmp = a[j];
                end = j - gap;
                while (end >= i)
                {
                    if (a[end] > tmp)
                    {
                        a[end + gap] = a[end];
                        end -= gap;
                    }
                    else break;
                }
                a[end+gap] = tmp;
            }
        }
    }
}
#else 
void shell_sort(int a[], int n)
{
    int gap = n;
    while (gap > 1)
    {
        gap /= 2;
        //多组并行
        for (int i = 0; i + gap < n; i++)
        {
            int tmp = a[i + gap];
            int end = i;
            while (end >= 0)
            {
                if (a[end] > tmp)
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else break;
            }
            a[end + gap] = tmp;
        }
    }
}
#endif

//二、选择排序
//2.1 选择排序
#ifdef SELECT_SORT_ORIGIN
void select_sort(int a[], int n)
{
    for (int i = 0; i < n; i++)
    {
        int Min_i = i;
        // 1. 单趟找最小元素的下标
        for (int j = i; j < n; j++)
        {
            if (a[Min_i] > a[j])
            {
                Min_i = j;
            }
        }
        // 2. 与i下标对应的元素交换
        std::swap(a[Min_i], a[i]);
    }
}
#else
void select_sort(int a[], int n)
{
    int l = 0, r = n - 1;
    while(l < r)
    {
        int Min_i = l, Max_i = r;
        // 1. 单趟找最小和最大元素的下标
        for (int j = l; j <= r; j++)
        {
            if (a[Min_i] > a[j])
            {
                Min_i = j;
            }
            if (a[Max_i] < a[j])
            {
                Max_i = j;
            }
        }
        // 2. 与l，r下标对应的元素交换
        std::swap(a[Min_i], a[l]);
        //存在情况：l指向的数就是目前区间的最大值
        if (l == Max_i)
        {
            Max_i = Min_i;
        }
        std::swap(a[Max_i], a[r]);
        l++, r--;
    }
}
#endif
//2.2 堆排序 -- 以大堆为例
void AdjustDown(int a[], int n, int father)
{
    //1. 找左孩子
    int left = 2 * father + 1;
    while (left < n)
    {
        int Maxchild = left;
        //2. 找右孩子
        if (left + 1 < n && a[Maxchild] < a[left + 1]) Maxchild = left + 1;
        //3. 与父亲比较
        if (a[Maxchild] > a[father])
        {
            std::swap(a[Maxchild], a[father]);
            father = Maxchild;
            left = 2 * father + 1;
        }
        else return;
    }
}
void heap_sort(int a[], int n)
{
    for (int i = n / 2; i >= 0; i--)
    {
        AdjustDown(a, n, i);
    }
    
    for (int i = 0; i < n - 1; i++)
    {
        std::swap(a[0], a[n - 1 - i]);
        AdjustDown(a, n-1-i, 0);
    }
}

//三、交换排序
//3.1 冒泡排序
#ifdef BUBBLE_SORT_ORIGIN
void bubble_sort(int a[], int n)
{
    for (int i = 0; i < n-1; i++)
    {
        //单趟从左向右，依次比较
        for (int j = 0; j < n - 1 - i; j++)
        {
            if (a[j] > a[j + 1]) std::swap(a[j], a[j + 1]);
        }
    }
}
#else
void bubble_sort(int a[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        int exchange = 0;
        //单趟从左向右，依次比较
        for (int j = 0; j < n - 1 - i; j++)
        {
            if (a[j] > a[j + 1])
            {
                std::swap(a[j], a[j + 1]);
                exchange = 1;
            }
        }
        if (exchange == 0) return;
    }
}
#endif
//双向冒泡排序
void two_bubble_sort(int a[], int n)
{
	int l = 0, r = n - 1, flag = 1;
	while (l < r)
	{
		for (int i = l; i < r; i++)
		{
			if (a[i] > a[i + 1])
			{
				std::swap(a[i], a[i + 1]);
				flag = i;
			}
		}
		r = flag;
		for (int i = r - 1; i >= l; i--)
		{
			if (a[i] > a[i + 1])
			{
				std::swap(a[i], a[i + 1]);
				flag = i;
			}
		}
		l = flag;
	}
}
//3.2 快速排序

#define QUICK_SORT_HOLE 1
#ifdef QUICK_SORT_ORIGIN
void quick_sort(int a[], int l, int r)
{
    if (l >= r) return;
    //1. 选key， 假设左边第一个为key
    int keyi = l;
    //2. 找到key的正确位置
    int st = l, ed = r;
    while (st < ed)
    {
        while (ed > st && a[ed] >= a[keyi]) --ed;
        while (ed > st && a[st] <= a[keyi]) ++st;
        std::swap(a[st], a[ed]);
    }
    //3. 将key交换到正确位置
    std::swap(a[st], a[keyi]);;
    keyi = st;
    //4. 继续下分
    quick_sort(a, l, keyi - 1);
    quick_sort(a, keyi + 1, r);
}
#elif QUICK_SORT_HOLE
void quick_sort(int a[], int l, int r)
{
    if (l >= r) return;
    //1. 选key， 假设左边第一个为key
    int key = a[l];
    int hole = l;
    //2. 找到key的正确位置
    int st = l, ed = r;
    while (st < ed)
    {
        while (ed > st && a[ed] >= key) --ed;
        a[hole] = a[ed];
        hole = ed;
        while (ed > st && a[st] <= key) ++st;
        a[hole] = a[st];
        hole = st;
    }
    //3. 将key交换到正确位置
    a[hole] = key;
    //4. 继续下分
    quick_sort(a, l, hole - 1);
    quick_sort(a, hole + 1, r);
}
#elif QUICK_SORT_POINTER
void quick_sort(int a[], int l, int r)
{
    if (l >= r) return;
    //1. 选key， 假设左边第一个为key
    int cur, prev, keyi;
    prev = keyi = l;
    cur = prev + 1;
    while (cur <= r) 
    {
        if (a[cur] < a[keyi] && ++prev != cur) 
        {
            std::swap(a[prev], a[cur]);
        }
        cur++;
    }
    std::swap(a[keyi], a[prev]);
    keyi = prev;
    quick_sort(a, l, keyi - 1);
    quick_sort(a, keyi + 1, r);
}
#elif QUICK_SORT_NONR
void quick_sort(int a[], int l, int r)
{
    std::stack<int> st;
    st.push(r);
    st.push(l);
    while (st.size())
    {
        int begin = st.top();
        st.pop();
        int end = st.top();
        st.pop();
        //单次快排过程
        int x = a[begin + end >> 1], i = begin - 1, j = end + 1;
        while (i < j)
        {
            do i++; while (a[i] < x);
            do j--; while (a[j] > x);
            if (i < j) std::swap(a[i], a[j]);
        }
        //插入新的划分段
        if (j + 1 < end)
        {
            st.push(end);
            st.push(j + 1);
        }
        if (begin < j)
        {
            st.push(j);
            st.push(begin);
        }
    }
}

#else
void quick_sort(int* a, int l, int r)
{
    if (l >= r) return;
    int x = a[l + r >> 1], i = l - 1, j = r + 1;
    while (i < j)
    {
        do i++; while (a[i] < x);
        do j--; while (a[j] > x);
        if (i < j) std::swap(a[i], a[j]);
    }
    quick_sort(a, l, j);
    quick_sort(a, j + 1, r);
}
#endif


// 归并排序

#ifdef MERGE_SORT_NONR
void merge_sort(int* a, int l, int r)
{
    int n = r - l + 1;
    int* tmp = new int[n];
    int gap = 1;//左右区间的大小
    while (gap < n)
    {
        for (int i = 0; i < n; i += 2 * gap)
        {
            // 开始归并, 左区间[i, i+gap-1] 右区间[i+gap, i+gap + gap-1] 起始位置 end = i
            int l1 = i, r1 = i + gap-1;
            int l2 = i + gap, r2 = i + 2 * gap - 1;
            int end = i;
            //情况1：r1 越界 表明l2,r2都越界了，直接break
            //情况2：l2 越界 同上，直接break
            //情况3: r2 越界 更改r2 = n-1
            //情况4：无越界 
            if (l2 >= n) break;
            if (r2 >= n) r2 = n - 1;
            while(l1 <= r1 && l2 <= r2)
            {
                if (a[l1] <= a[l2]) tmp[end++] = a[l1++];
                else tmp[end++] = a[l2++];
            }
            // 左区间可能有剩余
            while (l1 <= r1) tmp[end++] = a[l1++];
            // 右区间可能有剩余
            while (l2 <= r2) tmp[end++] = a[l2++];
            //这里用end - i，不要用2*gap， 因为存在越界的情况，拷贝的大小 <= gap*2
            memcpy(a + i, tmp + i, sizeof(int) * (end-i));
        }
        gap *= 2;
    }
    delete[] tmp;
}
#else
void _merge_sort(int a[], int l, int r, int tmp[])
{
    // 1. 终止条件
    if (l >= r)
        return;
    // 2. 不断递归划分
    int mid = l + r >> 1;
    _merge_sort(a, l, mid, tmp);
    _merge_sort(a, mid + 1, r, tmp);
    // 3. 开始归并, 左区间[l, mid] 右区间[mid+1, r] 起始位置 end = l
    int l1 = l, r1 = mid;
    int l2 = mid + 1, r2 = r;
    int end = l;
    while (l1 <= r1 && l2 <= r2)
    {
        if (a[l1] <= a[l2]) tmp[end++] = a[l1++];
        else tmp[end++] = a[l2++];
    }
    // 3.1 左区间可能有剩余
    while (l1 <= r1) tmp[end++] = a[l1++];
    // 3.2 右区间可能有剩余
    while (l2 <= r2) tmp[end++] = a[l2++];
    // 3.2 将排序好的数组拷贝到原数组内
    memcpy(a + l, tmp + l, sizeof(int) * (r - l + 1));
}
void merge_sort(int a[], int l, int r)
{
    int* tmp = new int[r-l+1];
    _merge_sort(a, l, r, tmp);
    delete[] tmp;
}
#endif
//基数排序
void radix_sort(int a[], int n)
{
    //确定基数 -- 按个 十...排序，因此基数 0-9 共10个
    const int radix = 10;
    std::queue<int> q[radix];
    int mol = 10;
    while (1)
    {
        //1. 分配
        for (int i = 0; i < n; i++)
        {
            //1. 求key
            // 10013 取十位 模100，再除10
            int k = a[i] % mol;
            k /= (mol / 10);
            //2. 入队
            q[k].push(a[i]);
        }
        // 如果都分配到q[0]则表示关键字序号已经超过k1, 
        if (q[0].size() == n) break;
        //2. 回收
        int end = 0;
        for (int i = 0; i < radix; i++)
        {
            while (q[i].size())
            {
                int t = q[i].front();
                q[i].pop();
                a[end++] = t;
            }
        }
        //3. 开始排序kd-1位
        mol *= 10;
    }
}
//计数排序
void count_sort(int a[], int n)
{
    int Max = a[0];
    for (int i = 1; i < n; i++)
    {
        Max = std::max(Max, a[i]);
    }
    int* count = new int[Max]{0};
    for (int i = 0; i < n; i++)
    {
        count[a[i]]++;
    }
    int end = 0;
    for (int i = 0; i <= Max; i++)
    {
        while (count[i])
        {
            a[end++] = i;
            count[i]--;
        }
    }
}